#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        if(nums.size()==1){
            return nums[0];
        }
        if(nums.size()==3){
            if(nums[0]==nums[1]){
                return nums[2];
            } else{
                return nums[0];
            }
        }
        if(nums[0]!=nums[1]){
            return nums[0];
        }
        int len=nums.size();
        int left=0;
        int right=len-1;
        int mid=0;
        while(left<right){
            mid=(left+right)/2;
            if(nums[mid]!=nums[mid+1]&&nums[mid]!=nums[mid-1]){
                return nums[mid];
            } else{
                if(mid%2==0&&nums[mid]==nums[mid-1]){
                    right=mid-1;
                }
                if(mid%2!=0&&nums[mid]==nums[mid-1]){
                    left=mid+1;
                }
                if(mid%2==0&&nums[mid]==nums[mid+1]){
                    left=mid+1;
                }
                if(mid%2!=0&&nums[mid]==nums[mid+1]){
                    right=mid-1;
                }
            }
            cout<<"left:"<<left<<",mid:"<<mid<<",right:"<<right<<endl;
        }
        return nums[left];
    }
};

int main(){
    Solution s;
    vector<int> in{1,1,2};
    cout<<s.singleNonDuplicate(in)<<endl;
    return 0;
}